<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3556：[Ctsc2014] 插线板</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2014] 插线板</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2014] 插线板</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Ctsc2014] 插线板                </h1>
                <p>时间限制：80s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>&nbsp;Allison有非常多的电子设备，比如iMac,iPod,iPhone和iPad。所以她准备购买插线板来给电子设备充电。在做了大量的网络调研后，</p>
<div>Allison拔线了一款美丽精巧的天翼牌排插（如左下图所示）。在见到这个插线板的第一眼，Allison就被它的境美造型所吸引，</div>
<div>于是她一次性购买了n个这种型号的插线板。&nbsp;</div>
<div>&nbsp;可是问题也随之而来，Allison的家中只有一个插座，她需要通过插线板的连接将电一层一层地导出（如右上图所示）。&nbsp;</div>
<div>插线板的连接方式是树形结构的：每个插线板的插头插在另一个插线板的插空中（除了根节点），插线板的连接不允许构成环。&nbsp;</div>
<div>每个插线板有火线，零线，地线三根导线，随着插线板数量的增加、倒显得磨损，电路中导线与导线之间接触产生的电阻已经到了</div>
<div>不能被忽视的地步。&nbsp;</div>
<div>如何来描述插线板的树形结构以及导线之间的电阻关系呢？Allison思考出来一个数学模型：用ai代表第i个插线板的编号，fi代表</div>
<div>第i个插线板的插头所差的插线板（即ai在树中的父亲），1代表火线，2代表零线，3代表地线，则整个网络的电阻可以用</div>
<div>R(ai,fi,x,y)(x,y&isin;{1,2,3})来描述，它代表ai的x线与fi的y线之间的电阻值（在这个数学模型中，Allison认为火线和领先也是</div>
<div>可能连接并且产生电阻的）下面是一个例子：&nbsp;</div>
<div>&nbsp;<img src="../file/3556_0.jpg" width="450" height="411" alt="" /></div>
<div>由于时间的推移，导线与导线之间的电阻还可能发生变化。现在，Allison想知道在插线板树形电路中，当前时刻ai插线板的x线和</div>
<div>aj插线板的y线之间的电阻式多少。规定插线板的树根节点不再插向其他插线板，且编号为1。&nbsp;</div></p><hr/><h3>输入格式</h3><p><p>&nbsp;第一行包含一个正整数n，表示插线板的个数。&nbsp;</p>
<div>接下来4(n-1)行，每4行为一个块。&nbsp;</div>
<div>第i块的第一行为一个整数fi【注：原题如此。实际应该是fi+1，下同】，表示编号为i+1的插线板的父亲为fi【注：同上】插线板。&nbsp;</div>
<div>接下来一个3*3的矩阵gxy，第x行第y个数表示编号为i+1的插线板的x线和fi【注：同上】的y线之间的电阻的倒数。&nbsp;</div>
<div>接下来一个整数q，表示q个操作数。&nbsp;</div>
<div>第一个整数位k，若k=1则接下来包含四个整数ai,xi,xj,g，表示将ai插线板的xi线与ai插线板的父亲fi</div>
<div>【注：原题如此。实际应该是fai】的xj线之间的电阻值改为g的倒数。保证2&lt;=ai&lt;=n。&nbsp;</div>
<div>若k=2，则接下来包含四个整数ai,xi,aj,xj，表示询问ai插线板的xi线与aj插线板的xj线之间的电阻大小。保证ai&ne;aj。&nbsp;</div></p><hr/><h3>输出格式</h3><p><p>对每个询问，输出一行实数，表示两条线之间的电阻。&nbsp;</p>
<div>若|(选手输出-标准输出)/标准输出|&lt;=10^-3，则被认为该电阻值正确，若所有电阻值皆正确，则可获得该测试点的得分。&nbsp;</div></p><hr/><h3>样例输入</h3><pre>3
1
6 7 1 
4 1 8 
8 3 3 
2
7 5 8 
10 5 7 
10 5 5 
10
1 3 1 2 2
1 2 2 3 5
2 3 2 2 2
1 2 3 2 5
1 3 1 2 3
2 1 2 2 3
1 3 2 1 2
2 2 1 1 1
1 2 1 2 5
2 3 1 1 2</pre><hr/><h3>样例输出</h3><pre>0.083836
0.095256
0.078828
0.146900</pre><hr/><h3>提示</h3><p><p>&nbsp;对于所有测试数据，输入保证是一棵树。0&lt;输入中电阻的倒数&lt;=10。&nbsp;</p>
<div>测试点编号 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;特点</div>
<div>&nbsp; &nbsp;1-6 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;n&lt;=100,q&lt;=1000，保证输入中只有查询没有修改</div>
<div>&nbsp; &nbsp;7-10 &nbsp; &nbsp; &nbsp; &nbsp; n&lt;=1000,q&lt;=1000，保证数据是一条链</div>
<div>&nbsp; &nbsp;11-16 &nbsp; &nbsp; &nbsp; &nbsp;n&lt;=10000,q&lt;=10000，保证数的高度不超过30</div>
<div>&nbsp; &nbsp;17-20 &nbsp; &nbsp; &nbsp; &nbsp;n&lt;=10000,q&lt;=10000</div>
<div></div></p><hr/><h3>题目来源</h3><p>鸣谢Vfleaking提供Spj</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3556" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3556" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>